package com.wangjie.stackandqueue;

import java.util.Stack;

/**
 * @author jieshao
 * @date 2022/5/18 22:52
 *
 * 1081. 不同字符的最小子序列
 */
public class Test12 {
    public static void main(String[] args) {
        String s = "bcabc";
        String res = smallestSubsequence(s);
        System.out.println(res);
    }

    public static String smallestSubsequence(String s) {
        // 记录去重后的结果
        Stack<Character> stack = new Stack<>();
        // 维护一个计数器，记录字符串中每个字符的数量，输入均为 ASCII 字符，大小 256 就够了
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        // 布尔数组，初始值为 false，记录栈中是否存在某个字符，输入均为 ASCII 字符，大小 256 就够了
        boolean[] inStack = new boolean[256];
        for (char c : s.toCharArray()) {
            // 每遍历一个字符，相应的计数减一
            count[c]--;
            // 若字符 c 在栈中存在，直接跳过
            if (inStack[c]) {
                continue;
            }
            // 插入之前，和前面的元素比较大小，若字典序比前面的小，pop 前面的元素
            while (!stack.empty() && stack.peek() > c) {
                // 若之后不存在栈顶元素了，停止 pop
                if (count[stack.peek()] == 0) {
                    break;
                }
                // 弹出栈顶元素，并把该元素标记为不在栈中
                inStack[stack.pop()] = false;
            }
            // 若字符 c 在栈中不存在，则插入栈顶，并标记为存在栈中
            stack.push(c);
            inStack[c] = true;
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.empty()) {
            sb.append(stack.pop());
        }
        // 栈中元素插入顺序是反的，需要 reverse 一下
        return sb.reverse().toString();
    }
}